import java.util.Arrays;

public class Myheap {
    public int[] arr;
    int size;
    public Myheap(){
        arr=new int[10];
    }
    public void init(int[] ret){
        for (int i=0;i<ret.length;i++){
            arr[i]=ret[i];
            size++;
        }
    }
    public void creatHeap(){
        for (int parent=(size-1-1)/2;parent>=0;parent--){
            shiftdown(parent,size);
        }
    }

    private void shiftdown(int parent, int length) {
        int child=parent*2+1;
        //有左孩子
        while (child<length){
            if (child+1<length&&arr[child+1]>arr[child]){
                //child为左右节点中较大的一个
                child=child+1;
            }
            if(arr[child]>arr[parent]){
                swap(child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }

    }

    private void swap(int child, int parent) {
        int tmp=arr[child];
        arr[child]=arr[parent];
        arr[parent]=tmp;
    }
    public void push(int val){
        if(size==arr.length){
            System.out.println("满了");
            return;
        }
        arr[size]=val;
        shiftup(size);
        size++;
    }

    private void shiftup(int child) {
        int parent=(child-1)/2;
        while (child>0){
        if (arr[child]>arr[parent]){
            swap(child,parent);
            child=parent;
            parent=(child-1)/2;
        }else break;

        }
    }
    public int pop(){
        if (size==0){
            return -1;
        }
        int top=arr[0];
        swap(0,size-1);
        size--;
        shiftdown(0,size);

        return top;

    }

}
